Numărul de drumuri în matrice

Introducere

Considerăm o matrice (labirint, teren, etc.) cu n linii și m coloane și un mobil aflat inițial în elementul de coordonate (1,1) – colțul stânga-sus, care se poate deplasa din elementul curent, de coordonate (i,j) în unul dintre elementele de coordonate (i+1,j) – aflat pe linia următoare, și (i,j+1) – aflat pe următoarea coloană. Să se determine în câte moduri poate ajunge mobilul în elementul de coordonate (n,m) – colțul dreapta-jos.

Problema are cel puțin două soluții, una care folosește metoda programării dinamice și una care se bazează pe combinatorică.

Rezolvare cu programare dinamică

Să constatăm mai întâi că numărul de drumuri căutat depinde de n și m – la mintea cocoșului, am putea spune. În general, numărul de drumuri de la poziția (1,1) la poziția (i,j) depinde de i și j, și numai de acestea. Atunci, formula recursivă care calculează rezultatul pentru (i,j) va depinde numai de i și de j!

Ne propunem să determinăm numărul de modalități în care mobilul ajunge de la poziția (1,1) în poziția (i,j). Fie acest număr \(F_{i,j}\). Constăm următoarele:

în orice element de pe linia 1 se poate ajunge într-un singur mod, dinspre stânga, deoarece în poziția (1,j) se poate ajunge numai din poziția (1,j-1). Astfel, \(F_{1,j} = 1\).
în orice element de pe coloana 1 se poate ajunge într-un singur mod, dinspre linia anterioară, deoarece în poziția (i,1) se poate ajunge numai din poziția (i-1,1). Astfel, \(F_{i,1} = 1\).
în poziția (i,j) (cu i>1 și j>1) se poate ajunge în două moduri:
- de sus, din poziția (i-1,j);
- din stânga, din poziția (i,j-1);
atunci numărul de posibilități de a ajunge în poziția (i,j) este numărul de posibilități de a ajunge în poziția (i-1,j) adunat cu numărul de posibilități de a ajunge în poziția (i,j-1). Astfel, \(F_{i,j} = F_{i-1,j} + F_{i,j-1}\).
rezultatul este \(F_{n,m}\).

În concluzie:

\( F_{i,j} = \begin{cases}
1& \text{dacă } i = 1 \text{ sau } j = 1, \\
F_{i-1,j} + F_{i,j-1}& \text{ dacă } i > 1 \text{ și } j > 1
\end{cases} \)

Deoarece formulele se suprapun, implementarea recursivă este foarte lentă. În consecință vom folosi o structură de date suplimentară, mai precis un tablou bidimensional în care A[i][j] reprezintă numărul de modalități de a ajunge din poziția (1,1) în poziția (i,j).

Acest tablou poate fi construit în maniera bottom-up:

int n, m, A[NN][NN];
...
for(int i = 1 ; i <= n ; ++ i)
	A[i][1] = 1;
for(int j = 1 ; j <= m ; ++ j)
	A[1][j] = 1;
for(int i = 2 ; i <= n ; ++ i)
	for(int j = 2 ; j <= m ; ++ j)
		A[i][j] = (A[i-1][j] + A[i][j-1]) % 9901;
cout << A[n][m];

De asemenea, recurența poate fi rezolvată în maniera top-down, cu memoizare:

int n, m, A[NN][NN];

int F(int i , int j)
{
    if(A[i][j] != 0)
        return A[i][j];
    if(i == 1 || j == 1)
        A[i][j] = 1;
    else
        A[i][j] = (F(i-1,j) + F(i,j-1)) % 9901;
    return A[i][j];
}
...
cout << F(n,m);

Rezolvare folosind calcul combinatorial

Pentru această soluție, să observăm că oricare traseu din poziția (1,1) în poziția (n,m), are respectă regulile de deplasare, va face exact n-1 pași spre dreapta și exact m-1 pași în jos. Traseele diferă numai prin ordinea acestor pași, nu prin numărul lor!

Atunci numărul de trasee este egal cu numărul de combinații de n-1 pași spre stânga și m-1 pași spre în jos; altfel spus n+m-2 pași, dintre care n-1 sunt în jos, adică: \(C_{n+m-2}^{n-1}\).

Observații

numărul de trasee crește foarte repede. Pentru valori relativ mici ale lui n și m se produce overflow. Pentru valori mai mari ale acestora este necesară implementarea operațiilor cu numere mari!
de multe ori, pentru a rezolva problema cu valori mai mari ale lui n și m, fără însă a implementa operații cu numere mari, se cere determinarea restului împărțirii rezultatului la o valoare dată MOD, adică realizarea operațiilor modulo MOD!
rezolvarea cu programare dinamică are complexitatea timp \(O(n \cdot m)\). Spațiul de memorie poate fi optimizat, folosind doar două tablouri unidimensionale, unul pentru linia curentă și celălalt pentru linia precedentă. Asta deoarece în calculul valorilor de pe linia curentă i se folosesc doar elemente de pe aceasta și de pe linia precedentă, i-1.
complexitatea rezolvării cu combinări este cea a algoritmului de determinare a combinărilor. Acestea pot fi determinate fie folosind formula uzuală, fie folosind triunghiul lui Pascal.

Numărul de drumuri în matrice

Introducere

Rezolvare cu programare dinamică

Rezolvare folosind calcul combinatorial

Observații

Probleme propuse